package algorithm.leetcode;

import algorithm.templates.ListNode;

public class NO24_两两交换链表中的节点 {
    class Solution {
        public ListNode swapPairs(ListNode head) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode cur = dummy;

            while (head != null && head.next != null) {
                // storage node temporary
                ListNode first = head, second = head.next;
                // jump two-step
                head = head.next.next;

                cur.next = second;
                second.next = first;
                first.next = head;
                cur = first;
            }
            return dummy.next;
        }
    }

    class RecursionSolution {
        public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            // head -> next -> remain section
            ListNode next = head.next;
            head.next = swapPairs(next.next);
            next.next = head;
            return next;
        }
    }
}
